#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>

#ifdef _OPENMP
  #include <omp.h>
#endif

using namespace std;

#pragma GCC optimize("-O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#ifndef BEHCH_MARK_THREADS
  #define BEHCH_MARK_THREADS 16
#endif

#define PRODUCTION_MAX 512
#define ITEM_MAX 128
#define VN_MAX 128
#define VT_MAX 128
#define STRING_MAX 1024

/**
 * record production like <0>::=<1><2>
 * @A:  <0>
 * @B:  <1>
 * @C:  <2>
**/
struct Production
{
  int A;
  int B;
  int C;
};

/**
 * record production like <0>::=<1>
 * @A:  <0>
 * @B:  <1>
**/
struct Item
{
  int A;
  char B;
};

/**
 * my list
**/
struct List
{
  unsigned num;
  int next;
  List (): num (0), next (-1) { }
  List (unsigned num, int next): num (num), next (next) { }
};

/**
 * used to index the sorted productions and items
 * @ptr:    means the subscript of production[] or item[]
 * @length: means the same type size
**/
struct Index
{
  int ptr;
  int size;
  Index (): ptr(-1), size(0) { }
} p_idx[VN_MAX][VN_MAX];

Production production[PRODUCTION_MAX];
Production production_pre[PRODUCTION_MAX];

int valid[VN_MAX];

Item item[ITEM_MAX];

// for items
int i_buckets[VT_MAX][ITEM_MAX];
int idx[VT_MAX];

List dp[STRING_MAX][STRING_MAX][VN_MAX];
int head[STRING_MAX][STRING_MAX];

int vn_num;
int production_num;
int item_num;
int string_length;
char str[STRING_MAX];

inline void add(int l, int r, int root, unsigned num)
{
  if (dp[l][r][root].num == 0 && dp[l][r][root].next == -1)
    dp[l][r][root] = {num, head[l][r]}, head[l][r] = root;
  else
    dp[l][r][root].num += num;
}

int main(int argc, char **argv)
{
  omp_set_num_threads (BEHCH_MARK_THREADS);
  memset (head, -1, sizeof (head));
  // basic io
  if (argc != 2)
  { printf ("cyk <input.txt>"); return 0; }

  freopen (argv[1], "r", stdin);
  scanf ("%d\n%d\n", &vn_num, &production_num);
  for (int i = 0; i < production_num; i++)
    scanf ("<%d>::=<%d><%d>\n", &production[i].A, &production[i].B, &production[i].C);
  scanf ("%d\n", &item_num);
  for (int i = 0; i < item_num; i++)
    scanf ("<%d>::=%c\n", &item[i].A, &item[i].B);
  scanf ("%d\n%s\n", &string_length, str);

  for (int i = 0; i < item_num; i++)
    i_buckets[(size_t)item[i].B][idx[(size_t)item[i].B]++] = item[i].A;
  
  for (int i = 0; i < string_length; i++)
    for (int j = 0; j < idx[(size_t)str[i]]; j++)
    {
      dp[i][i][i_buckets[(size_t)str[i]][j]] = {1, head[i][i]};
      head[i][i] = i_buckets[(size_t)str[i]][j];
    }
  
  sort (production, production + production_num, [](const Production& a,
                                                    const Production& b)
  { return a.B == b.B ? (a.C == b.C ? a.A < b.A : a.C < b.C) : a.B < b.B; });

  // init the index which indexed by [production.B][production.C]
  for (int i = 0; i < production_num; i++)
  {
    int n1 = production[i].B;
    int n2 = production[i].C;
    valid[n1] = valid[n2] = 1;
    if (p_idx[n1][n2].ptr == -1) p_idx[n1][n2].ptr = i;
    p_idx[n1][n2].size++;
  }

  // compute len in [2, string_length] situation
  for (int len = 2; len <= string_length; len++)
  {
    #pragma omp parallel for
    for (int l = 0; l <= string_length - len; l++)
    {
      int r = l + len - 1;
      List *llist, *rlist;
      for (int mid = l + 1; mid <= r; mid++)
      {
        // l tree root is i
        for (int lr = head[l][mid - 1]; lr != -1; lr = dp[l][mid - 1][lr].next)
        {
          // r tree root is j
          for (int rr = head[mid][r]; rr != -1; rr = dp[mid][r][rr].next)
          {
            if (p_idx[lr][rr].ptr == -1 || valid[lr] == 0 || valid[rr] == 0)
              continue;
            llist = &dp[l][mid - 1][lr];
            rlist = &dp[mid][r][rr];
            for (int k = p_idx[lr][rr].ptr;
                k < p_idx[lr][rr].ptr + p_idx[lr][rr].size; k++)
            {
              add (l, r, production[k].A, llist->num * rlist->num);
            }
          }
        }
      }
    }
  }

  printf("%u\n", dp[0][string_length - 1][0].num);
  return 0;
}
